package com.test.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;

class ListNode {
      int val;
      ListNode next;
     ListNode(int x) {
          val = x;
         next = null;
      }
  }
/**
 * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- 将元素 x 推入栈中。 pop() --
 * 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。
 * 
 * @author Administrator
 *
 */
class MinStack {

	private BlockingDeque<Integer> deque;
	private BlockingDeque<Integer> minDeque;

	/** initialize your data structure here. */
	public MinStack() {
		deque = new LinkedBlockingDeque<Integer>();
		minDeque = new LinkedBlockingDeque<Integer>();
	}

	public void push(int x) {
		deque.addFirst(x);

		if (minDeque.isEmpty()) {
			minDeque.addFirst(x);
		} else {
			if (minDeque.getFirst() > x) {
				minDeque.removeFirst();
				minDeque.addFirst(x);
			}
		}
	}

	public void pop() {
		Integer e = deque.removeFirst();
		if (minDeque.getFirst() == e) {
			minDeque.removeFirst();
		}
	}

	public int top() {
		return deque.poll();
	}

	public int getMin() {
		return minDeque.getFirst();
	}

	 public static void main(String[] args) {
		 String s1 = new String ("hello");
		 String s2 = new String ("hello");

		 System.out.println(s1==s2);
	// MinStack minStack = new MinStack();
	// minStack.push(-2);
	// minStack.push(0);
	// minStack.push(-3);
	// System.out.println(minStack.getMin()); // --> 返回 -3.
	// minStack.pop();
	// System.out.println(minStack.top()); // --> 返回 0.
	// System.out.println(minStack.getMin()); // --> 返回 -2.
	 }
}

public class Solution {

	/**
	 * 给定一个正整数，返回它在 Excel 表中相对应的列名称。
	 * 
	 * @param n
	 * @return
	 */
	public static String convertToTitle(int n) {

		String res = "";

		while (n > 0) {
			n--;
			int temp = n % 26;
			res = (char) (temp + 'A') + res;
			n /= 26;
		}

		return res;
	}

	public static void main(String[] args) {
		// System.out.println(majorityElement(new int[] {2,2,1,1,1,2,2}));;

//		System.out.println(convertToTitle(28));
		int[] res = twoSum(new int[]{2, 7, 11, 15},9);
		for (int i = 0; i < res.length; i++) {
			System.out.println(res[i]);
		}
		System.out.println();
	}
	/**
	 * 19. 删除链表的倒数第N个节点
	 * 
	 * @param head
	 * @param n
	 * @return
	 */
	public static ListNode removeNthFromEnd(ListNode head, int n) {

		ListNode first = head, second = head;

		while (n > 1) {
			if (first == second) {
				second = first.next;
			} else {
				second = second.next;
			}
			n--;
		}

		while (second.next != null) {
			first = first.next;
			second = second.next;
		}

		ListNode ret = head;
		while (head != first) {
			head = head.next;
			ret.next = head;
		}

		ret.next = head.next;
		return ret;

	}

	public static void main1(String[] args) {

		// System.out.println(10 >> 1);
		// test2();

		// System.out.println(threeSumClosest(new int[] { -1, 2, 1, -4 }, 1));

		ListNode aNode = new ListNode(1);
		aNode.next = new ListNode(2);
		aNode.next.next = new ListNode(3);
		aNode.next.next.next = new ListNode(4);
		aNode.next.next.next.next = new ListNode(5);
		
		removeNthFromEnd(aNode,2);

//		System.out.println(hasCycle(aNode));
	}

	/**
	 * 只出现一次的数字
	 * 
	 * 异或：相同为0，不同为1. 异或同一个数两次，原数不变。
	 * 
	 * @param nums
	 * @return
	 */
	public int singleNumber(int[] nums) {
		int res = 0;

		for (int i : nums) {
			res ^= i;
		}

		return res;
	}

	/**
	 * 环形链表
	 * 
	 * @param head
	 * @return
	 */
	public static boolean hasCycle(ListNode head) {
		Map<ListNode, Integer> map = new HashMap<ListNode, Integer>();
		if (head == null) {
			return false;
		}
		map.put(head, 1);

		while (head.next != null) {
			if (map.containsKey(head.next)) {
				return true;
			} else {
				map.put(head.next, 1);
			}
			head = head.next;
		}
		return false;

	}

	private static void test() {
		ListNode aNode = new ListNode(4);
		aNode.next = new ListNode(1);
		aNode.next.next = new ListNode(8);
		aNode.next.next.next = new ListNode(4);
		aNode.next.next.next.next = new ListNode(5);

		ListNode bNode = new ListNode(5);
		bNode.next = new ListNode(0);
		bNode.next.next = new ListNode(1);
		bNode.next.next.next = aNode.next.next;
		bNode.next.next.next.next = aNode.next.next.next;
		bNode.next.next.next.next.next = aNode.next.next.next.next;

		ListNode node = getIntersectionNode2(aNode, bNode);

		System.out.println(node.val);

	}

	private static void test2() {
		ListNode aNode = new ListNode(2);
		aNode.next = new ListNode(6);
		aNode.next.next = new ListNode(4);

		ListNode bNode = new ListNode(1);
		bNode.next = new ListNode(5);

		ListNode node = getIntersectionNode2(aNode, bNode);

		System.out.println(node.val);

	}

	/**
	 * 链表相交
	 * 
	 * 把a、b链表弄成等长，然后一起遍历，最先相等的结点就是交点。
	 * 
	 * @param headA
	 * @param headB
	 * @return
	 */
	public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {

		int aLen = 0, bLen = 0;
		ListNode aNode = headA, bNode = headB;

		if (aNode == null || bNode == null) {
			return null;
		}

		while (aNode.next != null) {
			aNode = aNode.next;
			aLen++;
		}
		while (bNode.next != null) {
			bNode = bNode.next;
			bLen++;
		}

		if (aNode != bNode) {
			return null;
		}

		aNode = headA;
		bNode = headB;

		if (aLen < bLen) {
			ListNode tempNode = aNode;
			aNode = bNode;
			bNode = tempNode;

			int tempLen = aLen;
			aLen = bLen;
			bLen = tempLen;
		}

		int i = 0;

		while (bLen + i != aLen) {
			aNode = aNode.next;
			i++;
		}

		while (aNode != null && bNode != null) {
			if (aNode == bNode) {
				return aNode;
			}
			aNode = aNode.next;
			bNode = bNode.next;
		}

		return null;

	}

	/**
	 * 链表相交
	 * 
	 * 双指针法
	 * 
	 * 这个思路就是 ListA + ListB = A + intersection + Bb + intersection ListB + ListA
	 * = Bb + intersection + A + intersection 用大A表示ListA里面非共有
	 * Bb表示listB里面非共有的，可以看到在第二个intersection的开头两个链表长度是一样的，必然相等
	 * 所以我们可以遍历A再遍历B，另一个遍历B再遍历A，两个指针必定在第二个交集处相遇，没有交集就是空指针
	 * 
	 * @param headA
	 * @param headB
	 * @return
	 */
	public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {

		ListNode pointerA = headA, pointerB = headB;

		while (pointerA != pointerB) {
			if (pointerA == null) {
				pointerA = headB;
			} else {
				pointerA = pointerA.next;
			}

			if (pointerB == null) {
				pointerB = headA;
			} else {
				pointerB = pointerB.next;
			}
		}

		return pointerA;

	}

	/**
	 * 两数之和 II - 输入有序数组
	 * 
	 * @param numbers
	 * @param target
	 * @return
	 */
	public static int[] twoSum(int[] numbers, int target) {

		int[] resArr = new int[2];

		Map<String, Integer> map = new HashMap<String, Integer>();

		for (int i = 0; i < numbers.length; i++) {

			int temp = numbers[i];
			if (map.containsKey(String.valueOf(target - temp)) && map.get(String.valueOf(target - temp)) != i) {
				resArr[0] = map.get(String.valueOf(target - temp)) + 1;
				resArr[1] = i + 1;// map.get(String.valueOf(temp));
			} else {
				map.put(String.valueOf(temp), i);
			}
		}

		return resArr;
	}

	/**
	 * 求众数
	 * 
	 * @param nums
	 * @return
	 */
	public int majorityElement(int[] nums) {

		Map<String, Integer> map = new HashMap<String, Integer>();
		for (int i : nums) {
			if (map.containsKey(String.valueOf(i))) {
				map.put(String.valueOf(i), map.get(String.valueOf(i)) + 1);
			} else {
				map.put(String.valueOf(i), 0);
			}
		}

		Set<Entry<String, Integer>> set = map.entrySet();

		Entry<String, Integer> res = null;

		for (Entry<String, Integer> entry : set) {
			if (res == null || res.getValue() < entry.getValue()) {
				res = entry;
			}
		}

		return Integer.parseInt(res.getKey());
	}

	// public static void main(String[] args) {
	// // System.out.println(majorityElement(new int[] {2,2,1,1,1,2,2}));;
	//
	// // System.out.println(convertToTitle(28));
	// int[] res = twoSum(new int[] { 2, 7, 11, 15 }, 9);
	// for (int i = 0; i < res.length; i++) {
	// System.out.println(res[i]);
	// }
	// System.out.println();
	// }

	// 16. 最接近的三数之和 - 暴力
	public static int threeSumClosest(int[] nums, int target) {
		int result = nums[0] + nums[1] + nums[2];
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				for (int k = j + 1; k < nums.length; k++) {
					int temp = nums[i] + nums[j] + nums[k];
					if (Math.abs(target - temp) < Math.abs(target - result)) {
						result = temp;
					}
				}
			}
		}
		return result;
	}

	// 16. 最接近的三数之和 - 排序：
	public static int threeSumClosest2(int[] nums, int target) {
		int result = nums[0] + nums[1] + nums[2];
		Arrays.sort(nums);
		for (int i = 0; i < nums.length; i++) {

		}
		return result;
	}
}
